﻿/*
题目：网格中的最短路径

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/?envType=study-plan-v2&envId=mihoyo-2023-fall-sprint
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // 表示坐标位置
    struct Place {
        int x;
        int y;
        int k;
    };
    static constexpr int dirs[5] = { 0, -1, 0, 1, 0 };

    // 最短路径，最多消除 k 个障碍物
    int shortestPath(vector<vector<int>>& grid, int k) {
        // memo[i][j][k] 表示到达 (i, j) 坐标，消除 k 个障碍物的 最少步骤  
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(m, vector<int>(k + 1, INT_MAX)));

        auto ok = [m, n](int x, int y) { return x >= 0 && x < n&& y >= 0 && y < m; };
        memo[0][0][0] = 0;

        // 队列，实现广度搜索
        queue<Place> q;
        q.push({ 0, 0, 0 });

        while (!q.empty()) {
            auto [x, y, removes] = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i];
                int ny = y + dirs[i + 1];
                if (!ok(nx, ny))            continue;

                // 如果是建筑物
                if (grid[nx][ny] == 1) {
                    // 这个路径不行
                    if (removes == k || memo[x][y][removes] + 1 >= memo[nx][ny][removes + 1]) {
                        continue;
                    }
                    memo[nx][ny][removes + 1] = min(memo[nx][ny][removes + 1], memo[x][y][removes] + 1);
                    q.push({ nx, ny, removes + 1 });
                }
                else { // 空地
                    if (memo[x][y][removes] + 1 >= memo[nx][ny][removes]) {
                        continue;
                    }
                    memo[nx][ny][removes] = min(memo[nx][ny][removes], memo[x][y][removes] + 1);
                    q.push({ nx, ny, removes });
                }
            }
        }

        auto res = *min_element(memo[n - 1][m - 1].begin(), memo[n - 1][m - 1].end());
        return res == INT_MAX ? -1 : res;
    }
};